package class_0909treap;

import java.util.Random;

/**
 * 了解一下Random类的用法
 * @author 毛民9527
 * @param <K> - 键的类型
 * @param <V> - 值的类型
 */
public class Treap<K extends Comparable<K>, V> {
    private static final Random random = new Random();
    public static class Node<K,V>{
        K key;
        V value;
        Node<K,V> left;
        Node<K,V> right;
        Node<K,V> p;
        int priority;
        public Node(K key, V value){
            this.key = key;
            this.value = value;
            priority = random.nextInt();
        }
    }
    Node<K,V> root;
    public Treap(){
        root = null;
    }
    public V search(K key){
        if(key == null){
            throw new IllegalArgumentException("key is null");
        }
        Node<K,V> cur = root;
        while(cur != null && key.compareTo(cur.key) != 0){
            if(cur.key.compareTo(key) < 0){
                cur = cur.right;
            }
            else{
                cur = cur.left;
            }
        }
       return cur==null?null:cur.value;
    }
    private static <K extends Comparable<K>,V>void leftRotate(Treap<K,V> T,Node<K,V> x){
        Node<K,V> y = x.right;
        x.right = y.left;
        if(y.left != null){
            y.left.p = x;
        }
        y.p = x.p;
        if(x.p == null){
            T.root = y;
        }
        else if(x == x.p.left){
            x.p.left = y;
        }
        else{
            x.p.right = y;
        }
        y.left = x;
        x.p = y;
    }
    private static <K extends Comparable<K>,V>void rightRotate(Treap<K,V> T,Node<K,V> y){
        Node<K,V> x = y.left;
        y.left = x.right;
        if(x.right != null){
            x.right.p = y;
        }
        x.p = y.p;
        if(y.p == null){
            T.root = x;
        }
        else if(y == y.p.left){
            y.p.left = x;
        }
        else{
            y.p.right = x;
        }
        x.right = y;
        y.p = x;
    }
    private static <K extends Comparable<K>,V>void UpRotate(Treap<K,V> T,Node<K,V> x){
        while(x != T.root && x.p.priority > x.priority){
            if(x.p.right == x){
                leftRotate(T, x.p);
            }
            else{
                // x.p.left == x
                rightRotate(T, x.p);
            }
        }
    }
    public void insert(K key, V value){
        if(root == null){
            root = new Node<>(key, value);
            return ;
        }
        Node<K,V> node = new Node<>(key, value);
        Node<K,V> p = null;
        Node<K,V> cur = root;
        while (cur != null) {
            p = cur;
            if (cur.key.compareTo(key) < 0) {
                cur = cur.right;
            } else if (cur.key.compareTo(key) == 0) {
                break;
            }
            else{
                cur = cur.left;
            }
        }
        node.p = p;
        if(p==null){
            root = node;
        }
        else if(p.key.compareTo(key) < 0){
            p.right = node;
        }
        else{
            p.left = node;
        }
        UpRotate(this, node);
    }
    private static <K extends Comparable<K>,V>void transplant(Treap<K,V> T, Node<K,V> u, Node<K,V> v) {
        if (u.p == null) {
            T.root = v;
            return ;
        }
        if(u.p.left == u) {
            u.p.left = v;
        }
        else {
            //u.p.right == u
            u.p.right = v;
        }
        if(v != null) {
            v.p = u.p;
        }
    }
    public Node<K, V> minInum(Node<K, V> head){
        if(head == null){
            return null;
        }
        while(head.left != null){
            head = head.left;
        }
        return head;
    }
    public void delete(K key) throws EmptyTreapException {
        if (key == null) {
            throw new IllegalArgumentException("key is null");
        }
        Node<K, V> cur = root;
        while (cur != null) {
            if (cur.key.compareTo(key) < 0) {
                cur = cur.right;
            } else if (cur.key.compareTo(key) == 0) {
                break;
            }
            else{
                cur = cur.left;
            }
        }
        if (cur == null) {
            return ;
        }
        if (cur.left == null) {
            transplant(this, cur, cur.right);
        }
        else if(cur.right == null) {
            transplant(this, cur, cur.left);
        }
        else{
            Node<K,V> succ = minInum(cur.right);
            if(succ != cur.right){
                transplant(this, succ, succ.right);
                succ.right = cur.right;
                cur.right.p = succ;
            }
            transplant(this, cur, succ);
            succ.left = cur.left;
            cur.left.p = succ;
            //这个操作--分步骤会影响优先级。
            downRotate(succ);
        }
    }
    private void downRotate(Node<K, V> parent) {
        while (parent.left != null || parent.right != null) {
            Node<K, V> child;

            // 选择优先级更高的子节点
            if (parent.left != null && parent.right != null) {
                child = (parent.left.priority < parent.right.priority) ? parent.left : parent.right;
            } else if (parent.left != null) {
                child = parent.left;
            } else {
                child = parent.right;
            }

            // 如果当前节点的优先级大于子节点，则进行旋转
            if (parent.priority > child.priority) {
                if (child == parent.left) {
                    Treap.rightRotate(this, parent);
                } else {
                    Treap.leftRotate(this, parent);
                }
            } else {
                break; // 满足堆的性质，终止循环
            }
        }
    }

}
